//欧拉函数phi(N)的含义表示从1~N中与N互质的数，如果k为质数，那么phi(k)=k-1，phi(1)=1
//欧拉函数的公式为phi(N)=N*[(p1-1)/p1]*[(p2-1)/p2]*...*[(pm-1)/pm]
//推导过程：因为phi(N)首先要把所有p1~pm的小于N的倍数筛去，然后再加上任意连个质因数的共同倍数之和，之后再加上...以此类推，之后提公因式即可
//需要注意的一点在于，由于欧拉函数的求值公式只需要质因数pk的值，不需要其出现的次数，所以不需要开任何东西来存储他
//适合单一欧拉函数的求解
#include <iostream>
using namespace std;

int n, a; //获取输入

int phi(int x)
{
    int res = x;
    for (int i = 2; i <= x / i; ++i)
        if (x % i == 0)
        {
            res = res / i * (i - 1); //注意，这里必须先除以i再乘以(i-1)，只有这样才能保证1/i能够被完整除去
            while (x % i == 0)
                x /= i;
        }
    if (x > 1)
        res = res / x * (x - 1);
    return res;
}

int main()
{
    // freopen("cin.txt", "r", stdin);
    cin >> n;
    while (n--)
    {
        cin >> a;
        cout << phi(a) << endl;
    }
    return 0;
}